package _interview100;

import _object.TreeNode;

/**
 * 543. 二叉树的直径
 */
public class No543 {
    private int ans;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftDeep = dfs(node.left);
        int rightDeep = dfs(node.right);
        ans = Math.max(ans, leftDeep + rightDeep);
        return Math.max(leftDeep, rightDeep) + 1;
    }
}
